package leetcode_1000;

import java.util.Stack;

/**
 *@author 周杨
 *SumOfSubarrayMinimums_907_ 给定一个int数组 问其中连续子数组的最小值的和 
 *describe:用栈的思想 AC 45%
 *2018年11月14日 下午8:49:53
 */
public class SumOfSubarrayMinimums_907_ {
	public static void main(String[] args) {
		SumOfSubarrayMinimums_907_ test=new SumOfSubarrayMinimums_907_();
		System.out.println(test.sumSubarrayMins1(new int[] {3,1,2,4}));
	}
	
	
	public int sumSubarrayMins(int[] A) {
		final int MOD=1_000_000_007;
		int res=0;
		int num=0;//栈内的全部值
		Stack<Integer> valueStack=new Stack<Integer>();
		Stack<Integer> countStack=new Stack<Integer>();
		for(int i=0;i<A.length;++i) {
			int count=1;//记录当前比其小的总个数
			while(!valueStack.isEmpty()) {
				if(valueStack.peek()<A[i]) {//这个元素比所有当前栈元素还大
					break;
				}
				else {//这个元素小于或者等于栈顶元素
					int value=valueStack.pop();
					int mount=countStack.pop();
					num-=mount*value;//把里面的值改变
					count+=mount;
				}
			}
			valueStack.add(A[i]);
			countStack.add(count);
			num+=A[i]*count;
			res=(res+num)%MOD;
		}
		return res;
	}
	
	/**
	 * describe:记录最短数字 TLE  91/100
	 * 2018年11月14日 下午8:04:56
	 */
	public int sumSubarrayMins1(int[] A) {
		final int MOD=1_000_000_007;
        int dp[]=new int[A.length];//dp[i]记录当前j-i最小值元素
        int res=0;
        for(int i=0;i<A.length;++i) {
        	dp[i]=A[i];
        	res=(res+A[i])%MOD;
        	for(int j=i-1;j>=0;--j) {
        		dp[j]=Math.min(dp[j], A[i]);
        		res=(res+dp[j])%MOD;
        	}
        }
        return res;
    }
}
